package com.cande.loki.exercise.algorithm;

import org.springframework.web.context.support.GroovyWebApplicationContext;

/**
 * @BelongsProject: loki
 * @BelongsPackage: com.cande.loki.exercise.algorithm
 * @Author: WANGAOFEI
 * @CreateTime: 2023-10-25  16:11
 * @Description: TODO 深度优先 岛屿问题
 * @Version: 1.0
 *
 */
public class DFSIslandNum {

        static int daoyu[][] =
                {
                        { 0, 0, 0, 0, 0, 0, 0, 0 },
                        { 0, 0, 1, 0, 0, 0, 0, 0 },
                        { 0, 1, 1, 1, 0, 0, 0, 0 },
                        { 0, 0, 1, 0, 0, 1, 1, 0 },
                        { 0, 0, 0, 0, 0, 1, 1, 0 },
                        { 0, 0, 1, 0, 0, 0, 0, 0 },
                        { 0, 0, 0, 0, 0, 0, 0, 1 },
                };

        public static void main(String[] args) {
            int count = 0;
            for (int i = 0; i < daoyu.length; i++)
                for (int j = 0; j < daoyu[i].length; j++)
                    if (daoyu[i][j] == 1) {
                        count++;
                        dfs(daoyu, i, j);
//                        lj(i, j);
                    }
            System.out.println("岛屿数量为:" + count);
        }
        static void dfs(int [] [] daoyu, int i ,int j) {
            int row = daoyu.length;
            int len = daoyu[0].length;
            if (i <0 || j <0 || i >= row || j >= len || daoyu[i][j] == 0) return;

            daoyu[i][j] = 0;
            dfs(daoyu,i+1, j);
            dfs(daoyu,i-1,j);
            dfs(daoyu,i,j+1);
            dfs(daoyu,i, j-1);

        }

        //不同写法 递归修改附近数值
        static void lj(int i, int j) {
            daoyu[i][j] = 2;
            // 上边
            if (i - 1 >= 0 && daoyu[i - 1][j] == 1)
                lj(i - 1, j);
            // 下边
            if (i + 1 < daoyu.length && daoyu[i + 1][j] == 1)
                lj(i + 1, j);
            // 左边
            if (j - 1 >= 0 && daoyu[i][j - 1] == 1)
                lj(i, j - 1);
            // 右边
            if (j + 1 < daoyu[i].length && daoyu[i][j + 1] == 1)
                lj(i - 1, j + 1);
        }

}
